import collections
class Solution(object):
    def numWays(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        DP = collections.deque([collections.defaultdict(int)] * 3)
        for i in range(n):
            if i == 0:
                DP[i] = collections.defaultdict(int)
                DP[i][1] += 1
            else:
                if i == 1:
                    DP[i] = collections.defaultdict(int)
                    DP[i][1] += 1
                    DP[i][2] += 1
                else:
                    DP[i % 3] = collections.defaultdict(int)
                    for key in DP[(i - 1) % 3]:
                        DP[i % 3][key + 1] += DP[(i - 1) % 3][key]
                    for key in DP[(i - 2) % 3]:
                        DP[i % 3][key + 1] += DP[(i - 2) % 3][key]
        d = DP[(n - 1) % 3]
        out = 0
        for key in d:
            out += d[key] * k * (k - 1) ** (key - 1)
        return out





data = Solution()
n = 2
k = 1
print(data.numWays(n, k))